<?php
//include_once("class_segment.php");
//include_once("class_unit.php");
//include_once("inc_str.php");
//include_once("inc_array.php");

class Tool_segment_light{

  public static function get_char(&$_str,$_offset){
    return mb_substr($_str,$_offset,1);
  }

  public static function tostring(&$_seg,&$_str){
    return mb_substr($_str,$_seg[0],$_seg[1]);
  }

  public static function tostringpartial(&$_seg,&$_str,$_len){
    return mb_substr($_str,$_seg[0],$_len);
  }
  
  public static function totruesegment(&$_seg,&$_str){
    return new Segment($_str,$_seg[0],$_seg[1]);
  }

  public static function toarrayletter(&$_seg,&$_str,&$_alphabet){
    $res=array();
    for($i=0;$i<$_seg[1];$i++){
      $l=self::get_char($_str,$i+$_seg[0]);
      $_alphabet[$l]=1;
      $res[]=$l;
    }
    return $res;
  }

  public static function toarrayrevletter(&$_seg,&$_str,&$_alphabet){
    $res=array();
    for($i=0;$i<$_seg[1];++$i){
      //$l=mb_substr($_str,$i+$_seg[0],1);
      //array_unshift($res,$l);
      $res[$_seg[1]-$i-1]=mb_substr($_str,$i+$_seg[0],1);
      if(!isset($_alphabet[$res[$_seg[1]-$i-1]]))
        $_alphabet[$res[$_seg[1]-$i-1]]=1;
    }
    return $res;
  }

  public static function get_same_prefix(&$_seg1,&$_seg2,&$_str1,&$_str2){
    $len=min($_seg1[1],$_seg2[1]);
    for($i=0;$i<$len && (mb_substr($_str1,$i+$_seg1[0],1)==mb_substr($_str2,$i+$_seg2[0],1));$i++);
    return $i;
  }

  public static function does_include_strict(&$_seg1,&$_seg2){
    //$ostart=$_seg2[0];
    //$offset_end=$offset_start+$_seg2[1];
    //$start=$_seg1[0];
    //$end=$start+$_seg1[1];
    return ($_seg1[0]+$_seg1[1]>=$_seg2[0]+$_seg2[1] and $_seg1[0]<=$_seg2[0]) ? true : false;
  }

//tri par longueur
 public static function usort_len($i,$j){
  if($i[1] < $j[1]) return -1;
  else return ($i[1] > $j[1]) ? 1 : 0;
 }

//tri par position
 public static function usort_offset($i,$j){
  if($i[0] < $j[0]) return -1;
  else return ($i[0] > $j[0]) ? 1 : 0;
 }

}

class suffixarray{
  private $array_str=array();
  private $array_suffix=array();
  private $array_repeated=array();
//  private $array_distrib=array();
  private $distrib=array();

  private $global_suffix=array();
  private $global_suffix_rev=array();
  private $res=array();
  private $res_rev=array();

  private $SA=array();

  private $global_equiv=array();
  private $corres_su_pr=array();
  private $global_equiv_rev=array();
  private $alphabet=array();
  private $n=0;
  private $lcp=array();

  public function __construct(){}

  public function __get_suffix($_i){
    return $this->array_suffix[$_i];
  }

  public function __get_str($_i){
    return $this->array_str[$_i];
  }

  public function __add_str(&$_str){
    $id_str=array_push($this->array_str,$_str)-1;
    $str_len=mb_strlen($_str);
    $mot=array();
    for($i=0;$i<$str_len;++$i){
      $this->array_suffix[]=array($i,$str_len-$i,$id_str);
      $mot[]=$l=mb_substr($_str,$i,1);
      $this->alphabet[$l]=1;
    }
    $this->n+=$str_len+1;
    $this->global_equiv[]=$mot;
    $this->global_equiv_rev=array_merge(array(array_reverse($mot)),$this->global_equiv_rev);
  }

  public function rstr($b,$e){
    $min=$this->lcp[$b];
    $minpos=array($b);
    $k=1;
    for($i=$b+1;$i<$e;++$i){
      if($min>$this->lcp[$i]){
        $min=$this->lcp[$i];
        $minpos=array($i);
        $k=1;
      }
      elseif($min == $this->lcp[$i]) $minpos[$k++]=$i;
    }
    if($min>0){
      $pos=array();
      for($i=$b-1;$i<$e;++$i) $pos[]=$i;
      $beg=$this->SA[$b-1];
      $corres=$this->n-($this->distrib_corres[$beg]+$min-1)-2;
      $cpt=array_push($this->array_repeated,array("pos"=>$pos))-1;
      $this->corres_su_pr[$corres][$min]=$cpt;
    }

    if($k != $e-$b){
      $ppos=$b;
      $minpos[$k++]=$e;
      for($i=0;$i<$k;++$i){
        if($minpos[$i]-$ppos>0) $this->rstr($ppos,$minpos[$i]);
        $ppos=$minpos[$i]+1;
      }
    }
//    print_r($this->array_repeated);
//    die();
  }

  public function sort_suffix(){
   echo "0 mem:".memory_get_usage(true)."\n";
   $start=microtime(true);
   $this->alphabet=array_keys($this->alphabet);
   sort($this->alphabet,SORT_STRING);
   $f=chr(1);
   $nf=chr(0);
//   $f=chr(ord(reset($this->alphabet))-1);  
//   $nf=chr(ord($f)-1);
   array_unshift($this->alphabet,$f);
   $distrib=array();
   $x=$k=0;

   foreach($this->global_equiv as $id_suffix=>$mot){
    foreach($mot as $lettre){
      $this->global_suffix[$k]=$lettre;
      $this->distrib_corres[$x]=$k;
      $this->distrib[$k++]=$x++;
    }
     $this->global_suffix[$k++]=$f;
   }

   unset($this->global_equiv);

   $this->global_suffix_rev=array_reverse($this->global_suffix,true);
   array_shift($this->global_suffix_rev);
   $this->global_suffix_rev[]=$f;

   $this->global_suffix[]=$this->global_suffix[]=$this->global_suffix[]=$nf;
   $this->global_suffix_rev[]=$this->global_suffix_rev[]=$this->global_suffix_rev[]=$nf;

   $time=microtime(true)-$start;
   echo "1 count :".count($this->global_suffix)."\n";
   echo "11 : $time\n";
   echo "11 mem:".memory_get_usage(true)."\n";

   $start=microtime(true);
   sortSuffixArray($this->global_suffix,$this->res,$this->n,$this->alphabet);
   $time=microtime(true)-$start;
   echo "12 : $time\n";
   echo "12 mem:".memory_get_usage(true)."\n";

   $start=microtime(true);
   sortSuffixArray($this->global_suffix_rev,$this->res_rev,$this->n,$this->alphabet);
   $time=microtime(true)-$start;
   unset($this->global_suffix_rev);
   unset($this->global_suffix);
   echo "13 : $time\n";
   echo "13 mem:".memory_get_usage(true)."\n";
  
   $start=microtime(true);
   $rank=$tmp=array();
   $k=0;
   for($i=0;$i<$this->n;++$i){
    if(isset($this->distrib[$this->res[$i]])){
      $tmp[$k]=$this->array_suffix[$this->distrib[$this->res[$i]]];
      $rank[$this->distrib[$this->res[$i]]]=$k;
      $this->SA[$k++]=$this->distrib[$this->res[$i]];
    }
   }
   unset($this->distrib);
   $time=microtime(true)-$start;
   echo "21 : $time\n";
   echo "21 mem:".memory_get_usage(true)."\n";

   $start=microtime(true);
   for($j=0;$j<$k;++$j){
     if($l>0)--$l;
     if($rank[$j]!=0){
       $segj=$this->array_suffix[$j];
       $segjj=$this->array_suffix[$this->SA[$rank[$j]-1]];
       while($l<$segj[1] and $l<$segjj[1] and
             mb_substr($this->array_str[$segj[2]],$l+$segj[0],1)==mb_substr($this->array_str[$segjj[2]],$l+$segjj[0],1)){
              ++$l; 
       }
     }
     else $l=0;
     $this->lcp[$rank[$j]]=$l;
   }

  $this->array_suffix=$tmp;
  unset($tmp);
  unset($rank);

  $this->lcp[$k]=0;
  $time=microtime(true)-$start;
  echo "22 : $time\n";
  echo "22 mem:".memory_get_usage(true)."\n";

  $start=microtime(true);
  $this->rstr(0,$k);
  $time=microtime(true)-$start;
  echo "23 : $time\n";
  echo "23 mem:".memory_get_usage(true)."\n";
  //unset($this->SA);
  unset($this->distrib_corres);
  unset($this->global_equiv_rev);
  unset($this->res);
  unset($this->lcp);
  unset($this->SA);
  echo "23 bis mem:".memory_get_usage(true)."\n";
//  die();
  }

  public function __init(){
    $start=microtime(true);
    $this->sort_suffix();
    $time=microtime(true)-$start;
//die();
    $start=microtime(true);
    $this->step3();
    $time=microtime(true)-$start;
//    echo "3 : $time\n";
    return $this->array_repeated;
    die();

    $start=microtime(true);
    $this->step5();
    $time=microtime(true)-$start;
    echo "5 : $time\n";
//    die();
    return $this->array_distrib;
  }
 
 private function step3(){
  echo "3 mem:".memory_get_usage(true)."\n";
//die();
  $start=microtime(true);
  $sorted=array();
  $flag=false;
  for($i=0;$i<$this->n;++$i){
    $o=$this->res_rev[$i];
    if(isset($this->corres_su_pr[$o])){
      ksort($this->corres_su_pr[$o]);
      foreach($this->corres_su_pr[$o] as $len=>$cpt){
        $info=array("len"=>$len,"pos"=>$this->array_repeated[$cpt]["pos"]);
        $su=$this->array_suffix[$info["pos"][0]];
        $su[1]=$len;
        if(isset($old_info)){
          if(count($old_info["pos"])!=count($info["pos"]) or
             !tool_segment_light::does_include_strict($su,$old_su)){
             $sorted[]=$old_info;
          }
        }
        $old_info=$info;
        $old_su=$su;
      }
      unset($this->corres_su_pr[$o]);
    }
  }
  $sorted[]=$old_info;
  $time=microtime(true)-$start;
  echo "3.1 : $time\n";
  echo "31 mem:".memory_get_usage(true)."\n";
  $this->array_repeated=$sorted;
  unset($this->res_rev);
  echo "31 bis mem:".memory_get_usage(true)."\n";
 }



 private function step3_usort_new($i,$j){
  if($i[2]<$j[2]) return -1;
  elseif($i[2]>$j[2]) return 1;
  else return $i[0]-$j[0];
}

 private function step5(){
  foreach($this->array_repeated as $i=>$r){
   $su=$this->array_suffix[$r["pos"][0]];
   $str=mb_substr($this->array_str[$su[2]],$su[0],$r["len"]);
   foreach($r["pos"] as $pos){
    $su=$this->array_suffix[$pos];
    $this->array_distrib[$str][]=new Segment($this->array_str[$su[2]],$su[0],$r["len"]);
   }
  }
  ksort($this->array_distrib,SORT_STRING);
 }

}

?>
